#include <fstream>
#include <forward_list>
#include <iostream>
#include <map>
#include <queue>
#include <exception>
struct pcb
{
    int id;
    int release_time;
    int priority;
    int cpu_time;
};
int main()
{
    std::ifstream file_reader("task");
    if (not file_reader)
        throw std::runtime_error("cannot open the file");
    if (file_reader.eof())
        return 0;
    std::forward_list<pcb> pcbs;
    pcb temp;
    file_reader >> temp.id >> temp.release_time >> temp.priority >> temp.cpu_time;
    pcbs.insert_after(pcbs.before_begin(), temp);
    for (std::forward_list<pcb>::iterator release_first(pcbs.begin());not file_reader.eof();)
    {
        file_reader >> temp.id >> temp.release_time >> temp.priority >> temp.cpu_time;
        if (temp.release_time == release_first->release_time)
        {
            std::forward_list<pcb>::iterator p(release_first), q(release_first);
            for (++p;p not_eq pcbs.end() and p->cpu_time < temp.cpu_time;++p, ++q);
            pcbs.insert_after(q, temp);
        }
        else
        {
            std::forward_list<pcb>::iterator p(release_first);
            for (++p;p not_eq pcbs.end();++p, ++release_first);
            pcbs.insert_after(release_first, temp);
            ++release_first;
        }
    }
    int time = 0;
    for (std::forward_list<pcb>::iterator p(pcbs.begin());;++p)
    {
        std::forward_list<pcb>::iterator q(std::next(p));
        if (q == pcbs.end())
            break;
        const int executed = q->release_time - time;
        const int left = p->cpu_time - executed;
        if (left > 0)
            if (q->cpu_time < left)//中断
            {
                pcb temp;
                temp.id = p->id;
                temp.priority = p->priority;
                temp.release_time = q->release_time + q->cpu_time;
                temp.cpu_time = left;
                p->cpu_time = executed;
                time = q->release_time;
                std::forward_list<pcb>::iterator before(q);
                for (++q;q not_eq pcbs.end() and q->release_time < temp.release_time;++q, ++before);
                for (;q not_eq pcbs.end() and q->release_time == temp.release_time and q->cpu_time < temp.cpu_time;++q, ++before);
                pcbs.insert_after(before, temp);
            }
            else//到了但不能中断
            {
                const int end_time = time + p->cpu_time;
                std::map<int, std::queue<pcb>> temp;
                for (std::forward_list<pcb>::iterator change(q);change != pcbs.end() and change->release_time <= end_time;++change)
                {
                    change->release_time = end_time;
                    temp[change->cpu_time].push(*change);
                }
                for (std::pair<const int, std::queue<pcb>>& bucket : temp)
                    for (;not bucket.second.empty();++q)
                    {
                        *q = bucket.second.front();
                        bucket.second.pop();
                    }
                time = end_time;
            }
        else
            time = q->release_time;
    }
    std::cout << "pid\tcpu_time\n";
    for (const pcb& p : pcbs)
        std::cout << p.id << '\t' << p.cpu_time << '\n';
    system("pause");
}
